#!/bin/env python
# vim:ts=4:sw=4


#
#	mpycache - a LRU Cache implementation in python
#	author: Saurav Mohapatra (mohaps@gmail.com)
#	website: http://code.google.com/p/mpycache
#	version: 1.0.0
#	date: 01/01/2010
#	license: Apache License 2.0 (http://www.apache.org/licenses/LICENSE-2.0.html)
#	Copyright (c) 2010 Saurav Mohapatra (mohaps@gmail.com)
#
#   Licensed under the Apache License, Version 2.0 (the "License");
#   you may not use this file except in compliance with the License.
#   You may obtain a copy of the License at
#
#       http://www.apache.org/licenses/LICENSE-2.0
#
#   Unless required by applicable law or agreed to in writing, software
#   distributed under the License is distributed on an "AS IS" BASIS,
#   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
#   See the License for the specific language governing permissions and
#   limitations under the License.
#

#
#   Release History:
#
#	   v 1.0.0 - initial release
#	   v 1.1.0 - fixed maxAge > 0 case return value bug and added versioning methods
#
#
import os;
import sys;
import time;

# a marker object to indicate not found
class _NotFound (object):
	def __init__(self):
		pass;
NOT_FOUND = _NotFound();

# a basic lru cache class

class LRUCache (object):
	DEBUG_DUMP_ENABLED = False;
	@classmethod
	def getVersionMajor(cls):
		return 1;
	@classmethod
	def getVersionMinor(cls):
		return 1;
	@classmethod
	def getVersionRelease(cls):
		return 0;
	@classmethod
	def getVersionTag(cls):
		return "maxAge fix";
	@classmethod
	def getVersionDetails(cls):
		return "v %d.%d.%d (%s)" % (cls.getVersionMajor(), cls.getVersionMinor(), cls.getVersionRelease(), cls.getVersionTag());
	@classmethod
	def currentTimeMicros(cls):
		return long(time.time() * 1000.0 * 1000.0);
	# -------------------------------------------------------------------------------------
	#	Create an LRU Cache. (Set maxSize/Age to 0 to turn off the pruning logic)
	#	maxSize = maximum number of elements to keep in cache
	#	maxAgeMs = oldest entry to keep 
	#	sizeElasiticity = allow cache to grow till maxSize + sizeElasticity before pruning
	# -------------------------------------------------------------------------------------
	def __init__(self, maxSize=32, maxAgeMs=0.0, sizeElasticity=10):
		self.maxSize = maxSize;
		self.maxAge = long(maxAgeMs * 1000.0);
		self.elasticity = sizeElasticity;
		self.cache = {};	# the actual cache Table
		self.keyTable = {}; # time vs. key
		self.timeStampTable = {}; #key vs. time
	# set key = value in cache
	def put(self, key, value):
		if value:
			self.cache[key] = value;
			self._freshen(key);
		self._prune();
	# get the value for key from cache (default to supplied value)
	def get(self, key, value=None):
		ret = self.cache.get(key, NOT_FOUND);
		# key was not found return default value
		if ret == NOT_FOUND:
			return value;
		# check if value is within acceptable age
		elif self.maxAge > 0:
			ts = self.timeStampTable[key];
			age = LRUCache.currentTimeMicros() - ts;
		
			if age > self.maxAge:
				self.erase(key);
				return value;
			else:
				self._freshen(key);
				return ret;
		# we found the key in cache return it
		else:
			self._freshen(key);
			return ret;
	# erase key
	def erase(self, key):
		if self.has_key(key):
			del self.cache[key];
			ts = self.timeStampTable[key];
			del self.timeStampTable[key];
			del self.keyTable[ts];
	# check if the key is present
	def has_key(self, key):
		return self.cache.has_key(key);
	# the cache current size
	def size(self):
		return len(self.cache);
	# clear the cache of all elements
	def clear(self):
		self.cache.clear();
		self.keyTable.clear();
		self.timeStampTable.clear();

	# "freshen" the key i.e. change the timestamp to current time
	def _freshen(self, key):
		oldTs = self.timeStampTable.get(key, NOT_FOUND);
		if not oldTs == NOT_FOUND:
			del self.timeStampTable[key];
			del self.keyTable[oldTs];
		newTs = LRUCache.currentTimeMicros(); 
		self.timeStampTable[key] = newTs;
		self.keyTable[newTs] = key;
			
	# we got to clear off all elements in excess of maxSize or maxAge
	def _prune(self):
		if self.maxSize == 0:
			pass;
		elif self.size()> (self.maxSize + self.elasticity):
			if LRUCache.DEBUG_DUMP_ENABLED:
				print 'size [%d] is greater than [%d]. pruning...' % (self.size(), self.maxSize + self.elasticity);
			toDel = self.size() - self.maxSize;
			#
			# TODO: need to improve this to some sort of constant time operation
			# mpycache was ported from a C++ implementation which leveraged
			# std::map<k,v> storing the keys sorted in order
			#
			timeStamps = sorted(self.keyTable.keys());
			timeStamps = timeStamps[0:toDel];
			for ts in timeStamps:
				key = self.keyTable[ts];
				del self.keyTable[ts];
				del self.timeStampTable[key];
				del self.cache[key];

	def __str__(self):
		ret = 'LRU Cache (cur=%d, max=%d (+%d),maxAge=%f ms)' % (self.size(), self.maxSize, self.elasticity, 0.001 * self.maxAge);
		return ret;
	#
	# a debug method to dump out the state of the cache
	#
	def dumpState(self, out=sys.stdout):
		
		out.write(str(self)+'\n');
		if not LRUCache.DEBUG_DUMP_ENABLED:
			return;
		if self.size() > 0:
			out.write('CACHE\n');
			for k,v in self.cache.items():
				out.write('   [%s]=[%s]\n'%(k,v));
			ts = LRUCache.currentTimeMicros();
			out.write('>> KEY TABLE\n');
			keys = sorted(self.keyTable.keys());
			for k in keys:
				out.write('   [%s]=[%s] (AGE=%d usec)\n'%(k,self.keyTable[k], ts - k));

			out.write('>> TSTAMP TABLE\n');
			for k,v in self.timeStampTable.items():
				out.write('   [%s]=[%s]\n'%(k,v));
			
			out.write('\n');
# sample usage
if __name__ == '__main__':
	# Turning on debug dump for detailed state dumps
	LRUCache.DEBUG_DUMP_ENABLED = True;

	print '>> Testing MPyCache ',LRUCache.getVersionDetails();

	# the lru cache
	lc = LRUCache(3,0.300,0);
	
	print 'initialized cache : '+str(lc);
	for i in range(0,10):
		lc.put('key'+str(i),'val'+str(i));
		print 'After add #'+str(i+1)+':';
		lc.dumpState();
		lc.put('key2','val2');

	print lc.get('key8');
	# let's dump the state of the cache
	lc.dumpState();
